The trend of achieving performance speedup through the use of multi-core and multi-processor architectures in computer systems, including printing systems, has gained widespread use in recent years. Multi-core and multi-processor architectures allow a number of threads belonging to one or more processes to execute in parallel across a number of CPUs, thereby reducing overall execution time.
In order to take advantage of such parallelism, a process is typically be broken down into “tasks”. A task is a well-defined portion of the overall process to be performed on given input data to produce some output data. The tasks of a process are largely independent and able to be executed in parallel.
The tasks executed in a renderer sub-system of a printing system commonly process different groups of graphic objects to produce intermediate representations for different portions of an input page specification. For example, the page area may be subdivided into y-bands, x-bands or tiles, and a task is assigned to each subdivision to process that part of the page. Alternatively to or in addition to spatial subdivision, objects may be subdivided into sub-sequences in drawing order (commonly referred to as z order) to form z-bands. A task is assigned to process each z-band.
In some printing systems, sequences of objects are converted into an intermediate representation of the graphics represented by the objects. Other tasks then merge the intermediate representations to form a final representation of the entire page. The final representation is then rendered to pixels that can be displayed or printed on an output device.
One method of representing the intermediate representation of a page is to utilize the outlines of the objects to divide the page into regions separated by pixel aligned edges. Each region has a corresponding fill compositing sequence that describes the operations required to render the pixels in the region. The fill compositing sequence consists of a sequence of fills with corresponding compositing operators, which are derived from properties of the objects that contribute to the region.
For pages with complex contents, the number of regions can be large, and thus the set of all fill compositing sequences can grow large, even if duplicates are removed. If a page is split into many z-bands and/or y-bands (or tiles), then a large proportion of intermediate representations generated from the bands have regions referencing similar sets of fill compositing sequences. It is therefore beneficial to keep fill compositing sequences in a single database while generating the intermediate representations and the final page representation. However, if the single database of fill compositing sequences needs to be updated frequently by multiple tasks producing intermediate representations or tasks merging the intermediate representations of a page and executing in parallel on multiple threads, frequent “locking” is required. Locking is a method of synchronising access to a shared resource by multiple parallel threads of execution. If multiple threads require access to the shared resource at the same time, only one thread may access the resource while the other threads are suspended. Frequent locking impairs the performance of a multithreaded system.
It is a common goal of multi-threaded systems to minimise frequent synchronised access to shared resources (sets of fill compositing sequences) while also minimising data (fill compositing sequences) that is duplicated in order to be used by multiple threads without synchronisation. Existing methods cannot efficiently address this goal in a multi-threaded rendering system.